package main.leetcode.clockin.March;

/**
 * 面试17.16.按摩师
 *
 * <p>一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
 *
 * <p>注意：本题相对原题稍作改动
 *
 * <p>
 *
 * <p>示例 1： 输入： [1,2,3,1] 输出： 4 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
 *
 * <p>示例 2： 输入： [2,7,9,3,1] 输出： 12 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
 *
 * <p>示例 3： 输入： [2,1,4,5,3,1,1,3] 输出： 12 解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-masseuse-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day24 {
    public static void main(String[] args) {
        System.out.println(new day24().massage(new int[] {2, 7, 9, 3, 1}));
    }
    // 动态规划
    //    public int massage(int[] nums) {
    //        int n = nums.length;
    //        if (n == 0) return 0;
    //        if (n == 1) return nums[0];
    //        if (n == 2) return Math.max(nums[0], nums[1]);
    //        int[] dp = new int[3];
    //        dp[0] = nums[0];
    //        dp[1] = nums[1];
    //        dp[2] = nums[0] + nums[2];
    //        int t;
    //        for (int i = 3; i < n; i++) {
    //            t = i % 3;
    //            dp[t] = Math.max(dp[t], dp[t == 2 ? 0 : t + 1]) + nums[i];
    //        }
    //        return Math.max(dp[0], Math.max(dp[1], dp[2]));
    //    }

    // 动态规划 优化
    // 我原本的思路是，dp[i]代表当前客人会被预约后的最大值
    // 优化后的思路是，dp[i]代表当前最大值，也就是不以当前客人被预约为前提
    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] dp = new int[3];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++)
            dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + nums[i]);
        return dp[(n - 1) % 3];
    }
}
